package org.example.struct.array2;

/**
 * @author liyishan
 * @date 2023/8/29 10:17
 * @apiNote
 */

public class Test00033Search {
    public static void main(String[] args) {
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
        System.out.println(test(nums, target));
    }

    public static int test(int[] nums, int target) {
        int n = nums.length;
        int cut = 0;
        for(int i = 0; i < n-1; i++){
            if(nums[i] > nums[i+1]){
                cut = i+1;
            }
        }
        int left = 0;
        int right = n-1;
        if(nums[right] < target){
            right  = cut-1;
        }else if(nums[left] > target){
            left = cut;
        }
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return -1;
    }


    public static int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, mid = 0;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
            if (nums[mid] >= nums[lo]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}
